1896G - Pepe Racing - CodeForces Solution

/*
 * author:  ADMathNoob
 * created: 11/25/23 09:50:16
 * problem: https://codeforces.com/contest/1896/problem/G
 */

/*
Comments about problem:


*/

#include <bits/stdc++.h>

using namespace std;

#ifdef _DEBUG
#include "debug.h"
#else
#define debug(...) 42
#endif

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  
  auto SolveTestCase = [&]() -> void {
    int n;
    cin >> n;
    
    auto Ask = [&](auto x) -> int {
      cout << '?';
      for (int i = 0; i < n; i++) {
        cout << ' ' << x[i] + 1;
      }
      cout << endl;
      int r;
      cin >> r;
      --r;
      auto it = find(x.begin(), x.end(), r);
      assert(it != x.end());
      return it - x.begin();
    };
    
    vector<deque<int>> groups(n);
    for (int g = 0; g < n; g++) {
      groups[g].resize(n);
      iota(groups[g].begin(), groups[g].end(), g * n);
    }
    
    auto SetHead = [&](auto& group) {
      int pos = Ask(group);
      swap(group[0], group[pos]);
    };
    
    for (int g = 0; g < n; g++) {
      SetHead(groups[g]);
    }
    vector<int> ret;
    // all heads became heads by winning a race, and are thus not slow
    for (int it = 0; it < n * n - (2 * n - 1); it++) {
      vector<int> heads(n);
      for (int g = 0; g < n; g++) {
        heads[g] = groups[g][0];
      }
      int h = Ask(heads);
      ret.push_back(heads[h]);
      groups[h].pop_front();
      for (int g = 0; g < n; g++) {
        if (g == h) {
          continue;
        }
        while (groups[h].size() < n && groups[g].size() >= 2) {
          groups[h].push_back(groups[g].back());
          groups[g].pop_back();
        }
      }
      if (groups[h].size() < n) {
        break;
      }
      SetHead(groups[h]);
    }
    vector<int> heads(n);
    vector<int> slow;
    for (int g = 0; g < n; g++) {
      heads[g] = groups[g][0];
      slow.insert(slow.end(), groups[g].begin() + 1, groups[g].end());
    }
    assert(slow.size() == n - 1);
    for (int it = 0; it < n - 1; it++) {
      SetHead(heads);
      ret.push_back(heads[0]);
      heads.erase(heads.begin());
      heads.push_back(slow.back());
      slow.pop_back();
    }
    ret.push_back(heads[0]);
    assert(ret.size() == n * n - n + 1);
    cout << '!';
    for (int r : ret) {
      cout << ' ' << r + 1;
    }
    cout << endl;
    // n to set up the groups
    // 2(n^2-n) to get the first n^2-n
    // 1 for the last one
    // 
  };
  
  {
    int tt;
    cin >> tt;
    for (int qq = 1; qq <= tt; qq++) {
      SolveTestCase();
    }
  }
  
  return 0;
}